<?php
/**
* 归并排序
*/
function mergeSort(&$arr, $left, $right) {
    
    if ($left < $right) {
        $mid = floor(($left + $right)/2);
        mergeSort($arr, $left, $mid);
        mergeSort($arr, $mid + 1, $right);
        echo $left . '--' . $mid . '--' . $right;
        merge($arr, $left, $mid, $right);
    }

}

/**
* @desc 合并
*/
function merge(&$arr, $left, $mid, $right) {
    
    $i = $left;
    $j = $mid + 1;
    $temp = [];
    while($i <= $mid && $j <= $right) {
        if ($arr[$i] < $arr[$j]) {
            $temp[] = $arr[$i++];
        } else {
            $temp[] = $arr[$j++];
        }
    }
    
    while($i <= $mid) {
        $temp[] = $arr[$i++];
    }

    while($j <= $right) {
        $temp[] = $arr[$j++];
    }
    //echo $left . '-' . $mid . '-' . $right;
    print_r($temp);   
    foreach($temp as $v) {
        $arr[$left++] = $v;
    }

}

$arr = [1,3,5,7,2,3,4,6,8];
mergeSort($arr, 0, count($arr) - 1);
print_r($arr);


?>
